#pragma once
#include<iostream>
#include<assert.h>

template<class T>
struct Node
{
    T _val;
    struct Node<T>* _next;
    Node(const T& val)
    :_val(val), _next(nullptr)
    {}
};

template<class T>
class list
{
    typedef Node<T> listNode;
public:
    list()
    {
        head = new listNode(T());
        tail = head;
    }
    listNode* find(T val)
    {
        assert(!empty());
        listNode* cur = head->_next;
        while(cur != nullptr)
        {
            if(cur->_val == val)
            {
                return cur;
            }
            cur = cur->_next;
        }
        return nullptr;
    }
    //默认尾插
    bool push(T val)
    {
        listNode* newNode = new listNode(val);
        if(newNode == nullptr)
        {
            return false;
        }
        tail->_next = newNode;
        tail = newNode;
        return true;
    }

    bool pushFront(T val)
    {
        listNode* newNode = new listNode(val);
        if(newNode == nullptr)
        {
            return false;
        }
        newNode->_next = head->_next;
        head->_next = newNode;
        return true;
    }
    //获取最后一个元素
    listNode* back()
    {
        assert(!empty());
        return tail;        
    }
    bool popFront(T val)
    {
        assert(!empty());
        if(head->_next == tail)
        {
            delete tail;
            tail = head;
        }
        else
        {
            listNode* next = head->_next;
            head->_next = head->_next->_next;
            delete next;
        }
        return true;
    }
    bool empty()
    {
        return tail == head;
    }
    void Print()
    {
        if(empty())
        {
            return;
        }
        listNode* cur = head->_next;
        while(cur != nullptr)
        {
            std::cout << cur->_val << " ";
            cur = cur->_next;
        }
        std::cout<<std::endl;
    }
private:
    listNode* head;   
    listNode* tail;  
};

